import java.util.*;
class topKFrequent {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++) {
            if(map.get(words[i]) == null) {
                map.put(words[i],1);
            }else {
                int val = map.get(words[i]);
                map.put(words[i],val+1);
            }
        }
        PriorityQueue<Map.Entry<String, Integer>> priorityqueue = new PriorityQueue<>(
                new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().equals(o2.getValue())) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String, Integer> entrie:map.entrySet()) {
            if(priorityqueue.size() < k) {
                priorityqueue.offer(entrie);
            }else {
                int val = priorityqueue.peek().getValue();
                String str1 = priorityqueue.peek().getKey();
                if(entrie.getValue() == val) {
                    if(str1.compareTo(entrie.getKey()) > 0) {
                        priorityqueue.poll();
                        priorityqueue.offer(entrie);
                    }
                }else {
                    if(entrie.getValue() > val) {
                        priorityqueue.poll();
                        priorityqueue.offer(entrie);
                    }
                }
            }
        }
        List<String> List = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            List.add(priorityqueue.poll().getKey());
        }
        Collections.reverse(List);
        return List;
    }
}